package 力扣.数组;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class 三个数的最大乘积628 {
    public static void main(String[] args) {
//        int[] ints = {1, 2, 3, 4};
//        int[] ints = {1,-4,100,-50};
//        int[] ints = {-100,-98,-1,2,3,4};
//        int[] ints = {0,0,0};
//        int[] ints = {-1,-2,-3};
        int[] ints = {1, 0 ,100,-1,-10};
        int i = maximumProduct4(ints);
        System.out.println(i);
    }

    public static int maximumProduct(int[] nums) {
        int length = nums.length;
//        System.out.println(Arrays.stream(nums).max().getAsInt());
        PriorityQueue pq = new PriorityQueue<Integer>(new Comparator<Integer>() {//通过重写抽象类Comparator中的compare方法可以更改比较方式
            @Override
            public int compare(Integer o1, Integer o2) {
                return  o1 - o2;//  o2 减去 o1：则是大根堆
            }
        });
        for (int i = 0; i < length; i++) {
            if (pq.size() < 3){
                pq.offer(nums[i]);
            }else {
                if ((int)pq.peek() < nums[i]){
                    pq.poll();
                    pq.offer(nums[i]);
                }
            }
        }
        System.out.println(pq);
        int re = 1;
        for (int i = 0; !pq.isEmpty() ; i++) {
            re *= (int)pq.poll();
        }
        return re;
    }
    public static int maximumProduct2(int[] nums) {
                Arrays.sort(nums);
                int n = nums.length;
                return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
    }

    /**
     * 只需找到最小的两个负数 和 最大的三个数
     * @param nums
     * @return
     */
    public static int maximumProduct3(int[] nums) {
        int length = nums.length;
        int l1 = 1;
        int l2 = l1;
        int h1 = Integer.MIN_VALUE;
        int h2 = h1;
        int h3 = h1;
        for (int i = 0; i < length; i++) {
            int te = nums[i];
            if (te < 0){
                if (te < l1){
                    if (te < l2){
                        int te1 = l2;
                        l2 = te;
                        l1 = te1;
                    }else {
                        l1 = te;
                    }
                }
            }
            if(te > h1){
                    if (te > h2){
                        if (te > h3){
                            int te1 = h2;
                            int te2 = h3;
                            h3 = te;
                            h2 = te2;
                            h1 = te1;
                        }else {
                            int te1 = h2;
                            h2 = te;
                            h1 = te1;
                        }
                    }else {
                        h1 = te;
                    }
                }
            }
        int re1 = l1 * l2 * h3;
        int re2 = h1 * h2 * h3;
        if (l1 != 1 && l2 != 1){
            return re1 >= re2 ? re1 : re2;
        }else {
            return re2;
        }

    }

    /**
     * 只需找到最小的两个数 和 最大的三个数
     * @param nums
     * @return
     */
    public static int maximumProduct4(int[] nums) {
                // 最小的和第二小的
                int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
                // 最大的、第二大的和第三大的
                int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

                for (int x : nums) {
                    if (x < min1) {
                        min2 = min1;
                        min1 = x;
                    } else if (x < min2) {
                        min2 = x;
                    }

                    if (x > max1) {
                        max3 = max2;
                        max2 = max1;
                        max1 = x;
                    } else if (x > max2) {
                        max3 = max2;
                        max2 = x;
                    } else if (x > max3) {
                        max3 = x;
                    }
                }

                return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}

